"""
插入排序的时间复杂度为O(n**2)
"""


def insert_sort(li):
    for x in range(1, len(li)):
        tmp = li[x]
        j = x - 1
        while j >= 0 and tmp < li[j]:
            li[j + 1] = li[j]
            li[j] = tmp
            j -= 1

    return li

def insert_sort_a(li):
    for x in range(1, len(li)):
        tmp = li[x]
        k = x - 1
        while k >= 0 and tmp < li[k]:
            li[k+1] = li[k]
            k -= 1
        li[k+1] = tmp
    return li

hh = [4, 64, 62, 7, 46, 464, 3]
print(insert_sort_a(hh))


